package algorithm.dp;



/**
 * @author shenenlu 2021年05月04日 上午00:20:56
 */
public class DpLearning {
    /**
     * 问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * @param n
     * @return
     */
    static int f( int n ){
        if(n <= 1)
            return n;
        // 先创建一个数组来保存历史数据
        int[] dp = new int[n+1];
        // 给出初始值
        dp[0] = 0;
        dp[1] = 1;
        // 通过关系式来计算出 dp[n]
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 把最终结果返回
        return dp[n];
    }



    public static void main(String[] args) {
        System.out.println(f(10));
    }

}
